\section{Heur\'istica de Busqueda Local}

%\subsection{Presentaci\'on del problema}

\subsection{Resoluci\'on}
Para la resoluci\'on del problema utilizando Heur\'isticas primero deb\'iamos generarnos una soluci\'n factible y luego definir nuestra vecindad.
Para generar la soluci\'on factible lo que realizamos fue utilizar una heur\'istica golosa que elije en cada paso una arista que forme el camino m\'inimo solo minimizando el valor de $w_1$ de la arista, si hubi\'esemos optado por realizarla minimizando por el valor de $w_2$ podr\'iamos obtener algo que no sea soluci\'on y no servir\'ia para la b\'usqueda local.
Una vez obtenido este camino que cumple con la cota $K$ que nos viene de entrada comenzamos con la b\'usqueda local. 
Para esto definimos como vecindad a los caminos posibles entre dos nodos que distan a 1 nodo (aquellos que estan a 2 aristas, o equivalentemente tienen un nodo entre los dos) de manera de ir mejorando el valor de $w_2$ al obtenido y la suma de $w_1$ siga siendo menor que $K$.
Para realizar esto en cada paso se tiene una suma total para $w_1$ y $w_2$ del total del camino, denomin\'emosla  SUMA\_W1 y SUMA\_W2, luego seleccionamos los primeros 3 nodos $(v_1,v_2,v_3)$ y nos guardamos el valor en otras dos variables de lo que ser\'ian:
$local\_w1 = SUMA\_W1 - valor\_W1(v1,v2) - valor\_W1(v2,v3)$  
$local\_W2 = SUMA\_W2 - valorW2(v_1,v_2) - valorW2(v_2,v_3)$
Luego buscamos otras 2 aristas que unan $v_1$ y $v_3$ mediante otro nodo $v_i$ que pertenezca al grafo, una vez encontrado, si el valor que den la suma de los $w_2$ de las aristas obtenidas a $local\_w2$ es menor a $SUMA\_w2$, y además los valores $w_1$ sumados a $local\_w1$ sea menor a $K$, es decir si 
$local\_w2 + valorw2(v_1,v_i) + valorw2(v_i,v3) < SUMA\_W2$ y
$local\_w2 + valorw2(v_1,v_i) + valorw2(v_i,v3) < K$
Entonces encontr\'e un nuevo camino y recorro as\'i todos los posibles caminos de $v_1$ a $v_3$. Una vez que se encontr\'o camino si es que exist\'ia otro se reemplaza y se contin\'ua con los siguientes 3 nodos siempre y cuando se pueda, siendo el primer nodo ahora $v_3$.
Una vez recorrido todo el camino se devuelve el nuevo camino que puede tener un valor total de la funci\'on $w_1$ mayor o igual pero el $w_2$ ser\'a menor o igual comparando con el camino que se toma como soluci\'on factible para la b\'usqueda local.

\subsection{Pseudoc\'odigo}

Soluci\'on es una 4-upla que contiene los siguientes elementos:
\begin{itemize}
\item $w_1$: que representa el valor total de $w_1$ de la soluci\'on.
\item $w_2$: que representa el valor total de $w_2$ de la soluci\'on.
\item $K$ que seria el valor de $K$ que debe respetar la soluci\'on.
\item $lista<int> camino$: que representa el camino de la soluci\'on.
\end{itemize}

Luego Grafo es una 3-upla que contiene los siguientes elementos:
\begin{itemize}
\item $int nodes$: la cantidad de nodos.
\item $vector<Edge> adjacencyMatrix$: la matriz de adyacencias.
\item $list<int> nodesOrder$: Es la lista de los nodos en orden.
\end{itemize}

Donde Edge es la 5-tupla con los siguientes elementos:
\begin{itemize}
\item $int id$: es el id del eje.
\item $int w1$: es el valor de w1 del eje.
\item $int w2$: es el valor de w2 del eje.
\item $int u$: nodo origen.
\item $int v$: nodo destino.
\end{itemize} 

\begin{pseudo}
  \func{ordenarJoyas}{Grafo G, int u , int v, int K}
  \tab soluci\'on camino = Dijkstra(G,u,v,k) \tOde{n^2}\\
  \tab BusquedaLocal(camino,G,u,v,k) \tOde{n^2}\\
\end{pseudo}
El algoritmo de Dijkstra es el algoritmo conocido levemente modificado que obtiene el camino de u a v siempre
y cuando que se cumpla que la suma de los $w_1$ de ese camino sea menor a $K$, en el caso de no existir tal camino no devuelve nada.\\
El algoritmo tiene una complejidad de $\Ode{n^2} + \Ode{n^2} = \Ode{n^2}$ \\
\begin{pseudo}
\func{BusquedaLocal}{solucion\, sol, Grafo\, G, int\, u , int\, v, int\, K}
	1-\tab int sumaActual= solucion.w2 \tOde{1}\\
	2-\tab bool encontre= false , termine = false \tOde{1}\\
	3-\tab iterador itFin,mid,itInicio \tOde{1}\\
	4-\tab itFin = itInicio = sol.Camino.begin() \tOde{1}\\
	5-\tab int SumaLocal = 0 \tOde{1}\\
	6-\tab int w1 = solucion.w1 \tOde{1}\\
	7-\tab list<int> original \tOde{1}\\
	8-\tab\WHILE(!termine)\\
	9-\tab\tab\IF(solucion.Camino.tam()<2) \tOde{1} \\
	10-\tab\tab\IF(itInicio $!=$ sol.camino.final() ) \tOde{1} \\
	11-\tab\tab\tab original.push_back(*itFin) \tOde{1}\\
	12-\tab\tab\tab itFin++ \tOde{1}\\
	13-\tab\tab\tab \IF(itFin $!=$ final) \tOde{1}\\
	14-\tab\tab\tab\tab original.push\_back(*itFin) \tOde{1}\\
	15-\tab\tab\tab\tab e = getEdge(G,*itInicio,*itFin,1) \tOde{1} \\
	16-\tab\tab\tab\tab \IF(e$!=$NULL) \tOde{1}\\
	17-\tab\tab\tab\tab\tab SumaLocal += e.w2 \tOde{1}\\
	18-\tab\tab\tab\tab\tab w1 $-= $ e.w1 \tOde{1}\\
	19-\tab\tab\tab\tab\tab mid = itFin \tOde{1}\\
	20-\tab\tab\tab\tab\tab itFin++ \tOde{1}\\
	21-\tab\tab\tab\tab\tab original.push\_back(*itFin) \tOde{1}\\
	22-\tab\tab\tab\tab\tab e = getEdge(G,*mid,*itFin,1) \tOde{1}\\
	23-\tab\tab\tab\tab\tab\IF(e!=NULL)\tOde{1}\\
	24-\tab\tab\tab\tab\tab\tab SumaLocal $+=$ e.w2 \tOde{1}\\
	25-\tab\tab\tab\tab\tab\tab w1 $-=$ e.w1 \tOde{1}\\
	26-\tab\tab encontre = buscarNuevo(original,G,cantNodos,K,sumaActual,SumaLocal, w1,nueva) \tOde{n}\\
	27-\tab\tab \IF(encontre) \tOde{1}\\
	28-\tab\tab\tab insertarNueva(itInicio,nueva,ItFin) \tOde{1}\\
	29-\tab\tab original.clear() \tOde{n}\\
	30-\tab\tab encontre = false \tOde{1}\\
	31-\tab\tab SumaLocal = 0 \tOde{1}\\
	32-\tab\tab itInicio = itFin \tOde{1}\\
	33-\tab\tab list<int>::iterator\, aux= itFin \tOde{1}\\
	34-\tab\tab aux++ \tOde{1}\\
	35-\tab\tab \IF(aux == sol.camino.end() || itFin == final) \tOde{1}\\
	36-\tab\tab\tab termine = true \tOde{1}\\
\end{pseudo}
- la funci\'on getEdge busca en la matriz de adyacencia por el \'indice del id de los nodos, esto se realiza en \Ode{1}
- el ciclo de las lineas 8-36 se ejecuta n/3 veces, la suma de las lineas dentro es de complejidad \Ode{n}, por lo tanto la complejidad es $n*n$, es decir
\Ode{$n^2$}.\\

\begin{pseudo}
\func{BusquedaLocal}{lista(int) caminolocal, Grafo G,int cantNodos,int K,int sumaActual,int SumaLocal,int  w1,int nueva}
1-\tab int sumaMinima = sumaLocal, minimo = -1 \tOde{1}\\
2-\tab int SumaNueva = sumaActual - sumaLocal \tOde{1}\\
3-\tab int w1 = w1Actual; Edge* ein, eout \tOde{1}\\
4-\tab \FOR (int i =0;i$<G$.nodes;i++)\\
5-\tab\tab Edge*	e = getEdge(G,original.front(),i,1) \tOde{1}\\
6-\tab\tab Edge*	e2 = getEdge(G,original.back(),i,1) \tOde{1}\\
7-\tab\tab \IF(e!= NULL && e2!= NULL) \tOde{1}\\
8-\tab\tab\tab \IF(($e.v == e2.u || e.u == e2.v || e.v == e2.v | e.u == e2u) &&$ \\
10-\tab\tab\tab ($e.w2 + e2.w2 < sumaMinima && e-w1 + e2.w1 + w1 < K $)) \tOde{1}\\
11-\tab\tab\tab\tab minimo = i \tOde{1}\\
12-\tab\tab\tab\tab sumaMinima = e.w2 + e2.w2 \tOde{1}\\
13-\tab\tab\tab\tab ein = e \tOde{1}\\
14-\tab\tab\tab\tab eout = e2 \tOde{1}\\
15-\end{pseudo}
-El ciclo de las lineas 4-15 se ejecuta n veces y por lo tanto la complejidad del ciclo es \Ode{n}.\\
-El total de la funcion es \Ode{1}.\\

\subsection{Analisis Heuristica}
Para esta Heur\'istica existen muchos casos en los cuales no se obtiene una soluci\'on \'optima ya que al partir de una soluci\'on que se obtiene por otro algoritmo, el problema para obtener la \'optima m\'as trivial de ver a simple vista es cuando nuestra soluci\'on inicial tenga caminos de que disten de m\'as de 1 nodo de distancia y que nos devuelva m\'as soluciones factibles, en algunos casos mejores, as\'i como las soluciones que podr\'ian existir eliminando el nodo que haya entre medio de los que selecciona la b\'usqueda local.
Por este motivo pensamos que la heur\'istica no es buena pero si bien en complejidad algor\'itmica supera ampliamente al exacto acerc\'andose a una soluci\'on \'optima lo mejor posible. Podr\'ia pensarse como una buena alternativa a una algoritmo exacto, a su vez pensamos que a partir de esta heur\'istica se puede obtener otras que busque caminos de 2 o m\'as nodos de distancia pero esto implicar\'ia agregar mucha complejidad al algoritmo ya que para cada uno de sus adyacentes deber\'ia recorrer los adyacentes y as\'i sucesivamente, este ciclo se realiza $n$ veces multiplicado en cada nivel con lo cual esto implicar\'ia que el algoritmo no ser\'ia mejor pero podr\'
ian obtenerse en algunos casos soluciones que sean con menor valor en el total de $w_1$ y $w_2$ del camino que nuestra heu\'istica.



\subsection{Experimentaci\'on}
La experimentaci\'on se realiz\'o en base a grafos armados de manera random, los mismos se crearon mediante un script en python que se encuentra dentro de la carpeta \"src\" llamado generador.py. Se generaron 500 instancias con nodos que se eleg\'ian de manera random entre 5 y 200, en base a la cantidad de nodos se gener\'o el grafo completo y se tom\'o 3/4 de las aristas para que no sea el grafo completo ya que si todos los nodos eran adyacentes entre si y no serv\'ia esa entrada. Los valores $w_1$ y $w_2$ de las aristas son n\'umeros random entre 1 y 100 , el valor de $K$ se genera al final luego de sumar todas los valores de $w_1$ de las aristas saco el promedio y lo multiplico por un valor estimado por distancia entre nodos suponiendo que los nodos est\'an m\'as pr\'oximos si la numeraci\'on es pr\'oxima.

\includegraphics[scale=0.8]{local.jpg} \\
Como se puede observar el algoritmo tiene un orden de complejidad polinomico de \Ode{n^2}, se puede ver que en muchos casos de tamaño de entrada grande el tiempo de ejecuci\'on es chico esto puede ser porque no encontr\'o camino o porque el camino era trivial de encontrar.
Para tomar la complejidad se tuvo en cuenta el algoritmo que genera la soluci\'on factible y luego la que realiza la b\'usqueda local, ambas tienen misma complejidad y no afecta la b\'usqueda local a el total del algoritmo.

\subsection{C\'odigo de fuente}
\begin{verbatim}
void busquedaLocal(Result* R,Graph* G,int cantNodos, int u,int v,int K){

    int sumaActual= R->w2;
    int nueva = -1;
    bool encontre;
    list<int>::iterator itFin = R->C.begin();
    list<int>::iterator itInicio = R->C.begin();
    list<int>::iterator mid;
    list<int>::iterator final = R->C.end();
    final--;

    bool termine = false;
    int SumaLocal = 0;
    int w1 = R->w1;
    list<int> original;
    Edge *e;


    while(!termine){

        if(R->C.size()<2){
                break;
        }



        if(itInicio != final){

            original.push_back(*itFin);
            itFin++;
            if(itFin != final){
                original.push_back(*itFin);
                e = getEdge(G,*itInicio,*itFin,1);
                if(e!=NULL){
                    SumaLocal += e->w2;
                    w1 -= e->w1;

                    mid = itFin;
                    itFin++;
                    original.push_back(*itFin);
                    e = getEdge(G,*mid,*itFin,1);
                    if(e!=NULL){
                        SumaLocal += e->w2;
                        w1 -= e->w1;
                    }
                }

            }
        }
        //Busco mejor camino

        encontre = buscarNuevo(original,G,cantNodos,K,sumaActual,SumaLocal,w1,nueva);

        //Cambio en la lista si encontre

        if(encontre){
            //Muevo el puntero siempre y cuando pueda
            list<int>:: iterator aux = itInicio;
            aux++;
            R->C.erase(aux);
            aux = itInicio;
            aux++;
            R->C.insert(aux, nueva);

            R->w2 = sumaActual;
            R->w1 = w1;

        } //FIN IF ENCONTRE
        original.clear();
        encontre = false;
        SumaLocal = 0;
        itInicio = itFin;
        //Limpio la lista auxiliar que usa la busqueda de los vecinos

        //adelanto los punteros y reviso si puedo avanzar
        list<int>::iterator aux= itFin;
        aux++;
        if(aux == final || itFin == final) {
            termine = true;
        }

    } //FIN WHILE
}
\end{verbatim}
